package 力扣._22_括号生成;

import java.util.*;

class Solution {
    public List<String> generateParenthesis(int n) {
        // 先试试DP , dp[i] , i对括号的所有组合
        List<List<String>> dp = new LinkedList<>();
        // dp[k] = ( dp[i] ) + dp[j]  i<=j<k&& i+j==k-1
        List<String> t0 = new LinkedList<>();
        t0.add("");

        //初始化
        dp.add(t0);
        for (int k = 1; k <= n; k++) {
            List<String> now = new LinkedList<>();
            for (int i = 0; i < k; i++) {
                List<String> list_i = dp.get(i);
                List<String> list_j = dp.get(k-1 - i);
                for (String s1 : list_i) {
                    for (String s2 : list_j) {
                        now.add("("+s1+")"+s2);
                    }
                }

            }
            dp.add(now);

        }
        return dp.get(n);
    }

    public static void main(String[] args) {
        System.out.println(new Solution().generateParenthesis(3));

    }
}